# -*- coding:utf-8
# 5366. 检查网格中是否存在有效路径 显示英文描述
# 用户通过次数1
# 用户尝试次数4
# 通过次数1
# 提交次数4
# 题目难度Medium
# 给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是：
#
# 1 表示连接左单元格和右单元格的街道。
# 2 表示连接上单元格和下单元格的街道。
# 3 表示连接左单元格和下单元格的街道。
# 4 表示连接右单元格和下单元格的街道。
# 5 表示连接左单元格和上单元格的街道。
# 6 表示连接右单元格和上单元格的街道。

from typing import List
class Solution:
    def __init__(self):
        self._visited = []
        self._dic = {}
        self._grid = []
        self._m = 0
        self._n = 0

    def isValid(self,rr,cc):
        return rr>=0 and rr< self._m and cc>=0 and cc<self._n

    def isPassed(self,r,c,p0,p1):##这个点能否回到原点？
        dd = self._grid[p0][p1]
        d0,d1 = self._dic[dd]
        xx0,yy0 = d0
        xx1,yy1 = d1
        if p0+yy0 == r and p1+xx0 == c:
            return True
        if p0+yy1 == r and p1+xx1 == c:
            return True
        return False




    def dfs(self,r,c):
        self._visited[r][c] = 1
        print("r,c:",r,c)

        if r == self._m - 1 and c == self._n - 1:
            return True
        else:
            dir = self._grid[r][c]
            dir0,dir1 = self._dic[dir]
            x0,y0 = dir0
            x1,y1 = dir1
            res0,res1 = False,False
            np0, np1 = r + y0, c + x0
            if self.isValid(np0,np1) and self._visited[np0][np1] == 0 and self.isPassed(r,c,np0,np1):
                res0 = self.dfs(np0,np1)
            newp0,newp1 = r+y1,c+x1
            if self.isValid(newp0,newp1) and self._visited[newp0][newp1] == 0 and self.isPassed(r,c,newp0,newp1):
                res1 = self.dfs(newp0,newp1)
            print("n0+n1",np0+np1,newp0+newp1)
            if np0+np1 == self._m + self._n-1 or newp0+newp1 == self._m+self._n-1:
                return True

            return res0 or res1



    def hasValidPath(self, grid: List[List[int]]) -> bool:
        self._m = grid.__len__()
        self._n = grid[0].__len__()
        self._dic = {1:[(1,0),(-1,0)],
               2:[(0,1),(0,-1)],
               3:[(-1,0),(0,1)],
               4:[(1,0),(0,1)],
               5:[(0,-1),(-1,0)],
               6:[(0,-1),(1,0)]}

        self._grid = grid
        self._visited = [[0 for j in range(grid[0].__len__()) ] for i in range(grid.__len__())]

        return self.dfs(0,0)

## dfs爆炸了，下面是LeetCode的bfs算法
#
# class Solution:
#     def hasValidPath(self, grid):
#
#         dir = {1: [(0, 1), (0, -1)],
#                2: [(1, 0), (-1, 0)],
#                3: [(1, 0), (0, -1)],
#                4: [(0, 1), (1, 0)],
#                5: [(0, -1), (-1, 0)],
#                6: [(0, 1), (-1, 0)]}
#
#         x, y = 0, 0
#         m, n = len(grid), len(grid[0])
#         if x == m - 1 and y == n - 1:
#             return True
#         from collections import deque
#         queue = deque([(x, y)])
#         while queue:
#             x, y = queue.popleft()
#             for dx, dy in dir[grid[x][y]]:
#                 nx, ny = x + dx, y + dy
#                 if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != -1:  # 判断边界条件
#                     for ndx, ndy in dir[grid[nx][ny]]:
#                         if ndx + dx == 0 and ndy + dy == 0:  # 判断连通性
#                             if nx == m - 1 and ny == n - 1:  # 判断是否到达终点
#                                 return True
#                             queue.append((nx, ny))
#             grid[x][y] = -1  # 访问过的结点赋-1(之后不再重复访问)
#         return False



res = Solution().hasValidPath([[1,1,2]])
print(res)